package item18;

import org.junit.Test;

/**
 * @author Lv Jing
 * @date 2018年07月18日 23:40
 */
public class DeleteNode {

    private Solution solution = new Solution();

    /**
     * 删除节点在中间
     */
    @Test
    public void test01() {
        LinkNode head = new LinkNode(1, new LinkNode(2, new LinkNode(3, null)));
        LinkNode delete = head.next;
        Solution.printLinkNode(head);
        solution.deleteNode(head, delete);
        Solution.printLinkNode(head);
    }

    /**
     * 删除节点在尾部
     */
    @Test
    public void test02() {
        LinkNode head = new LinkNode(1, new LinkNode(2, new LinkNode(3, null)));
        LinkNode delete = head.next.next;
        Solution.printLinkNode(head);
        solution.deleteNode(head, delete);
        Solution.printLinkNode(head);
    }

    /**
     * 链表只有一个节点
     */
    @Test
    public void test03() {
        LinkNode head = new LinkNode(1, null);
        Solution.printLinkNode(head);
        solution.deleteNode(head, head);
        Solution.printLinkNode(head);
    }
}
class Solution {

    /**
     * 面试题18-1：在O(1)时间内删除某一链表节点
     * 思路：正常情况下，我们删除某一链表节点，常规做法是从头开始对链表进行遍历，直到遍历到的节点的next为指定删除节点，就能进行删除了。
     * 但是这样遍历的时间复杂度为O(n)，不符合题目要求，可以换一种思路。
     * 比如要删除的节点为i，它的下一个节点为j，那么把j的value复制到i的位置，然后把i的next指向j的next，这时就相当于删除了节点i。
     * h--i--j      h--j--j--k      h--j--k
     * 但是如果删除节点为尾节点，它的next为null，那么这种情况只能顺序遍历进行删除；如果链表只有一个节点，那么直接删除节点就好，然后
     * 把头结点指向null。
     * 也就是需要分三种情况，正常情况（删除节点非尾节点），链表足够长但是删除节点为尾节点，链表只要一个节点。这样的平均时间复杂度就是O(1)
     * 同时该题没有考虑待删除节点不在链表中的情况，若考虑上，那么必然涉及全链表遍历，不符合题目要求，这个视情况而定。
     */
    public void deleteNode(LinkNode head, LinkNode toBeDelete) {
        if (head == null || toBeDelete == null) {
            return;
        }

        if (toBeDelete.next != null) {
            // 非尾节点，可以直接替换删除
            LinkNode nextNode = toBeDelete.next;
            toBeDelete.value = nextNode.value;
            toBeDelete.next = nextNode.next;
        } else if (head == toBeDelete) {
            // 链表只要一个节点，直接删除即可
            head.value = 0;
        } else {
            // 待删除节点为尾节点，需要全表遍历删除
            LinkNode node = head;
            while (node.next != toBeDelete) {
                node = node.next;
            }
            node.next = null;
        }
    }

    public static void printLinkNode(LinkNode head) {
        LinkNode node = head;
        while (node != null) {
            System.out.print(node.value);
            System.out.print("|");
            node = node.next;
        }
        System.out.println();
    }
}
class LinkNode {
    public int value;
    public LinkNode next;

    public LinkNode() {
    }

    public LinkNode(int value, LinkNode next) {
        this.value = value;
        this.next = next;
    }
}